package q2334_validSubarraySize;

import java.util.ArrayDeque;
import java.util.Arrays;

public class Solution_2 {
    /*
    栈的方法就相对很好理解
    对于每一个元素nums[i] 分别找到其左右第一个小于它的元素的位置i, j 长度为 k
    那么对于i - j这一段的元素其最小值即为nums[i]
    所以只要nums[i] > threshold / k 那么这一段元素必然是满足要求的
     */
    public int validSubarraySize(int[] nums, int threshold) {
        int n = nums.length;
        int[] left = new int[n]; // left[i] 为左侧第一个小于 nums[i] 的元素位置（不存在时为 -1）
        ArrayDeque<Integer> st = new ArrayDeque<>();
        for (var i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop();
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        var right = new int[n]; // right[i] 为右侧第一个小于 nums[i] 的元素位置（不存在时为 n）
        st = new ArrayDeque<>();
        for (var i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop();
            right[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        for (var i = 0; i < n; ++i) {
            var k = right[i] - left[i] - 1;
            if (nums[i] > threshold / k) return k;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 6, 3, 5, 8, 9};
        var n = nums.length;
        var left = new int[n]; // left[i] 为左侧第一个小于 nums[i] 的元素位置（不存在时为 -1）
        var st = new ArrayDeque<Integer>();
        for (var i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop();
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }
        System.out.println(Arrays.toString(left));
    }
}
